/*
 * @lc app=leetcode.cn id=33 lang=cpp
 * @lcpr version=30204
 *
 * [33] 搜索旋转排序数组
 */

// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution
{
public:
    int search(vector<int> &nums, int target)
    {
        int n = nums.size();
        if (n == 0)
        {
            return -1;
        }

        if (n == 1)
        {
            return nums[0] == target ? 0 : -1;
        }

        int left = 0;
        int right = n - 1;
        while (left <= right)
        {
            int mid = (left + right) >> 1;
            if (nums[mid] == target)
            {
                return mid;
            }

            // 中间值大于等于首元素的值，说明0到mid这一段是大的增区间，
            if (nums[left] <= nums[mid])
            {
                // 目标值落在这段大的增区间上，右边界向左挪动
                if (nums[left] <= target && target < nums[mid])
                {
                    right = mid - 1;
                }
                // 目标值比这段大的增区间还要大或者是在小的增区间上，都要将左边界向右挪动
                else
                {
                    left = mid + 1;
                }
            }
            // mid到n-1这一段是小的增区间
            else
            {
                // 目标值落在小的增区间上，挪动左边界
                if (nums[mid] < target && target <= nums[right])
                {
                    left = mid + 1;
                }
                // 目标值比小的增区间还要小或者比小的增区间大，都要将右边界向左挪动
                else
                {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
};
// @lc code=end

/*
// @lcpr case=start
// [4,5,6,7,0,1,2]\n0\n
// @lcpr case=end

// @lcpr case=start
// [4,5,6,7,0,1,2]\n3\n
// @lcpr case=end

// @lcpr case=start
// [1]\n0\n
// @lcpr case=end

 */
